//给你一个仅由小写英文字母组成的字符串 s 。 
//
// 如果一个字符串仅由单一字符组成，那么它被称为 特殊 字符串。例如，字符串 "abc" 不是特殊字符串，而字符串 "ddd"、"zz" 和 "f" 是特殊字
//符串。 
//
// 返回在 s 中出现 至少三次 的 最长特殊子字符串 的长度，如果不存在出现至少三次的特殊子字符串，则返回 -1 。 
//
// 子字符串 是字符串中的一个连续 非空 字符序列。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "aaaa"
//输出：2
//解释：出现三次的最长特殊子字符串是 "aa" ：子字符串 "aaaa"、"aaaa" 和 "aaaa"。
//可以证明最大长度是 2 。
// 
//
// 示例 2： 
//
// 
//输入：s = "abcdef"
//输出：-1
//解释：不存在出现至少三次的特殊子字符串。因此返回 -1 。
// 
//
// 示例 3： 
//
// 
//输入：s = "abcaba"
//输出：1
//解释：出现三次的最长特殊子字符串是 "a" ：子字符串 "abcaba"、"abcaba" 和 "abcaba"。
//可以证明最大长度是 1 。
// 
//
// 
//
// 提示： 
//
// 
// 3 <= s.length <= 5 * 10⁵ 
// s 仅由小写英文字母组成。 
// 
//
// Related Topics 哈希表 字符串 二分查找 计数 滑动窗口 👍 28 👎 0


package LeetCode.editor.cn;

import java.util.*;

/**
 * @author ldltd
 * @date 2024-06-04 14:52:41
 * @description 2982.找出出现至少三次的最长特殊子字符串 II
 */
public class FindLongestSpecialSubstringThatOccursThriceIi{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 FindLongestSpecialSubstringThatOccursThriceIi fun=new FindLongestSpecialSubstringThatOccursThriceIi();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 //和I的区别是，字符串的长度可能很长
    public int maximumLength(String s) {
		char[] ar = s.toCharArray();
		List<Integer > []g=new ArrayList[26];
		Arrays.setAll(g,i->new ArrayList<>());
		int cnt=0;
		for (int i = 0; i < ar.length; i++) {
			cnt++;
			if(i+1==s.length()||ar[i]!=ar[i+1]){
				//统计每个字符到这个位置的最长长度,
				g[ar[i]-'a'].add(cnt);
				cnt=0;
			}
		}
		int res=0;
		for (List<Integer> list : g) {
			if(list.isEmpty()) continue;
			//降序排序
			list.sort(Collections.reverseOrder());
			//防止不够比较，至少有两个为0的
			list.add(0);
			list.add(0);
			/*最大值，三种情况
			1.当前字符最长长度里，-2，比如 aaaaaaa长度为7，可以取不同的三个长度为5的aaaaa
			2.或者从最长和第二长里，如果第一长和第二长一样
			可以取三个最长-1，如果最长比第二长大，取三个第二长如，有aaaaa aaaa，可以三个aaaa
			可以统一写为min(a[0]-1,a[1])
			3.或者从最长第二第三长取一个第三长的
			*/
			res= Math.max(res,Math.max(list.get(0)-2,
					Math.max(Math.min
							(list.get(0)-1,list.get(1)),list.get(2))));
		}
		return res>0?res:-1;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
